{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Number After Mutating Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子字符串突变后可能得到的最大整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>num</code> ，该字符串表示一个大整数。另给你一个长度为 <code>10</code> 且 <strong>下标从 0&nbsp; 开始</strong> 的整数数组 <code>change</code> ，该数组将 <code>0-9</code> 中的每个数字映射到另一个数字。更规范的说法是，数字 <code>d</code> 映射为数字 <code>change[d]</code> 。</p>\n",
    "\n",
    "<p>你可以选择 <strong>突变</strong>&nbsp; <code>num</code> 的任一子字符串。<strong>突变</strong> 子字符串意味着将每位数字 <code>num[i]</code> 替换为该数字在 <code>change</code> 中的映射（也就是说，将 <code>num[i]</code> 替换为 <code>change[num[i]]</code>）。</p>\n",
    "\n",
    "<p>请你找出在对 <code>num</code> 的任一子字符串执行突变操作（也可以不执行）后，可能得到的 <strong>最大整数</strong> ，并用字符串表示返回。</p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是字符串中的一个连续序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = \"<strong><em>1</em></strong>32\", change = [9,8,5,0,3,6,4,2,6,8]\n",
    "<strong>输出：</strong>\"<strong><em>8</em></strong>32\"\n",
    "<strong>解释：</strong>替换子字符串 \"1\"：\n",
    "- 1 映射为 change[1] = 8 。\n",
    "因此 \"<strong><em>1</em></strong>32\" 变为 \"<strong><em>8</em></strong>32\" 。\n",
    "\"832\" 是可以构造的最大整数，所以返回它的字符串表示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = \"<strong><em>021</em></strong>\", change = [9,4,3,5,7,2,1,9,0,6]\n",
    "<strong>输出：</strong>\"<strong><em>934</em></strong>\"\n",
    "<strong>解释：</strong>替换子字符串 \"021\"：\n",
    "- 0 映射为 change[0] = 9 。\n",
    "- 2 映射为 change[2] = 3 。\n",
    "- 1 映射为 change[1] = 4 。\n",
    "因此，\"<strong><em>021</em></strong>\" 变为 \"<strong><em>934</em></strong>\" 。\n",
    "\"934\" 是可以构造的最大整数，所以返回它的字符串表示。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = \"5\", change = [1,4,7,5,3,2,5,6,9,4]\n",
    "<strong>输出：</strong>\"5\"\n",
    "<strong>解释：</strong>\"5\" 已经是可以构造的最大整数，所以返回它的字符串表示。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>num</code> 仅由数字 <code>0-9</code> 组成</li>\n",
    "\t<li><code>change.length == 10</code></li>\n",
    "\t<li><code>0 &lt;= change[d] &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-number-after-mutating-substring](https://leetcode.cn/problems/largest-number-after-mutating-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-number-after-mutating-substring](https://leetcode.cn/problems/largest-number-after-mutating-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"132\"\\n[9,8,5,0,3,6,4,2,6,8]', '\"021\"\\n[9,4,3,5,7,2,1,9,0,6]', '\"5\"\\n[1,4,7,5,3,2,5,6,9,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfStringPairs(self, words: List[str]) -> int:\n",
    "        the_others: Set[str] = set(words)\n",
    "        n_pairs: int = 0\n",
    "\n",
    "        for word in words:\n",
    "            the_others.discard(word)\n",
    "            rev: str = \"{:s}{:s}\".format(word[1], word[0])\n",
    "            if rev in the_others:\n",
    "                n_pairs += 1\n",
    "\n",
    "        return n_pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfStringPairs(self, words: List[str]) -> int:\n",
    "        return sum(i == j[::-1] for i_index, i in enumerate(words) for j in words[i_index+1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfStringPairs(self, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        for i in words:\n",
    "            if i[::-1] in words and i != i[::-1]:\n",
    "                ans += 1\n",
    "        return int(ans/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfStringPairs(self, words: List[str]) -> int:\n",
    "        sum=0\n",
    "        for i in words:\n",
    "            \n",
    "            m=i[::-1]\n",
    "            if m!=i:\n",
    "                if m in words:\n",
    "                    sum+=1\n",
    "            \n",
    "            \n",
    "                \n",
    "            \n",
    "            \n",
    "        return sum//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:      \n",
    "        flag=0\n",
    "        s=\"\"\n",
    "        for i,n in enumerate(num):\n",
    "            if change[int(n)]>int(n):\n",
    "                s1=str(change[int(n)])\n",
    "                s+=s1\n",
    "                flag=1\n",
    "            elif change[int(n)]<int(n) and flag==1:\n",
    "                s+=num[i:]\n",
    "                break\n",
    "            else:\n",
    "                s+=n\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        res = ''\n",
    "        flag = False \n",
    "        for i in range(n):\n",
    "            cur = int(num[i])\n",
    "            if change[cur] > cur:\n",
    "                flag = True\n",
    "                res += str(change[cur])\n",
    "            else:\n",
    "                if flag and change[cur] != cur:\n",
    "                    break\n",
    "                res += num[i]\n",
    "        return res + num[len(res):]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        c = 0\n",
    "        for i in range(len(num)):\n",
    "            k = int(num[i])\n",
    "            if change[k] > k:\n",
    "                num = num[:i] + str(change[k]) + num[i+1:]\n",
    "                c = 1\n",
    "            elif change[k] < k:\n",
    "                if c:\n",
    "                    return num\n",
    "        return num\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        l = len(num)\n",
    "        for i in range(l):\n",
    "            if int(num[i])<change[int(num[i])]:\n",
    "                c = str(change[int(num[i])])\n",
    "                count = 1\n",
    "                while i+count<l and int(num[i+count])<=change[int(num[i+count])]:\n",
    "                    c += str(change[int(num[i+count])])\n",
    "                    count += 1\n",
    "                return num[0:i] + c + num[i+len(c)::]\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        ans = ''\n",
    "\n",
    "        for i, ch in enumerate(num):\n",
    "            if ch < str(change[int(ch)]):\n",
    "                idx = i\n",
    "                while idx < n and num[idx] <= str(change[int(num[idx])]):\n",
    "                    ans += str(change[int(num[idx])])\n",
    "                    idx += 1\n",
    "                ans += num[idx:]\n",
    "                break\n",
    "            ans += ch\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        #print(str(change[3]))\n",
    "        res=''\n",
    "        flag=0\n",
    "        for i in range(0,len(num)):\n",
    "            if change[int(num[i])]>int(num[i]):\n",
    "                res+=(str(change[int(num[i])]))\n",
    "                flag=1\n",
    "            elif change[int(num[i])]==int(num[i]):\n",
    "                res+=(num[i])\n",
    "                \n",
    "            else:\n",
    "                if flag==1:\n",
    "                    res+=num[i:]\n",
    "                    break\n",
    "                res+=(num[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        set_sml = set()\n",
    "        set_big = set()\n",
    "        for i,x in enumerate(change):\n",
    "            if i > x:\n",
    "                set_sml.add(i)\n",
    "            if x > i:\n",
    "                set_big.add(i)\n",
    "        # print(set_sml)\n",
    "        cnt = 0\n",
    "        stt = len(num)+1\n",
    "        for x in num: \n",
    "            if int(x) in set_big:\n",
    "                stt = cnt ##开始交换的位\n",
    "                break\n",
    "            cnt += 1\n",
    "        ##\n",
    "        cnt = 0\n",
    "        end = len(num)+1\n",
    "        for x in num[stt:]:\n",
    "            if int(x) in set_sml:\n",
    "                end = cnt+stt\n",
    "                break\n",
    "            cnt += 1\n",
    "        print(stt, end)  \n",
    "        ch = ''\n",
    "        for x in num[stt:end]:\n",
    "            ch += str(change[int(x)])\n",
    "        return num[:stt] + ch + num[end:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        l = len(num)\n",
    "        for i in range(l):\n",
    "            if int(num[i])<change[int(num[i])]:\n",
    "                c = str(change[int(num[i])])\n",
    "                count = 1\n",
    "                while i+count<l and int(num[i+count])<=change[int(num[i+count])]:\n",
    "                    c += str(change[int(num[i+count])])\n",
    "                    count += 1\n",
    "                print(c)\n",
    "                return num[0:i] + c + num[i+len(c)::]\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        i = 0\n",
    "        while i < n and int(num[i]) >= change[int(num[i])]: i += 1\n",
    "        if i == n: return num\n",
    "        ans = num[:i]\n",
    "        while i < n and int(num[i]) <= change[int(num[i])]:\n",
    "            ans += str(change[int(num[i])])\n",
    "            i += 1\n",
    "        ans += num[i:]\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        s = ''\n",
    "        flag = 0\n",
    "        for i in range(len(num)):\n",
    "            if int(num[i]) < change[int(num[i])]:\n",
    "                flag = 1\n",
    "                s += str(change[int(num[i])])\n",
    "                print(i)\n",
    "            elif int(num[i]) > change[int(num[i])]:\n",
    "                if flag == 0:\n",
    "                    s += num[i]\n",
    "                else:\n",
    "                    s += num[i:]\n",
    "                    break\n",
    "            else:\n",
    "                s += num[i]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        index = -1\n",
    "        for i in range(len(num)):\n",
    "            t = int(num[i])\n",
    "            c = change[t]\n",
    "            if c > t:\n",
    "                index = i\n",
    "                break\n",
    "        if index == -1:\n",
    "            return num\n",
    "        f = True\n",
    "        res = num[:index]\n",
    "        for i in range(index,len(num)):\n",
    "            t = int(num[i])\n",
    "            c = change[t]\n",
    "            if c>=t and f:\n",
    "                res += str(c)\n",
    "            else:\n",
    "                res += num[i]\n",
    "                f = False\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        ind = {str(i): str(w) for i, w in enumerate(change)}\n",
    "        ans = list(num)\n",
    "        n = len(num)\n",
    "        for i in range(n):\n",
    "            if ind[ans[i]] > ans[i]:\n",
    "                for j in range(i, n):\n",
    "                    if ind[ans[j]] >= ans[j]:\n",
    "                        ans[j] = ind[ans[j]]\n",
    "                    else:\n",
    "                        break\n",
    "                break\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        change = [*map(str, change)]\n",
    "        l = list(num)\n",
    "        start = False\n",
    "        for i, c in enumerate(num):\n",
    "            if c < change[int(c)] or (start and c == change[int(c)]):\n",
    "                start = True\n",
    "                l[i] = change[int(c)]\n",
    "            elif start:\n",
    "                break\n",
    "        return ''.join(l)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        ans = []\n",
    "        pre = -1\n",
    "        for x in num:\n",
    "            if pre != 0 and change[ord(x) - ord('0')] > ord(x) - ord('0'):\n",
    "                ans.append(chr(ord('0') + change[ord(x) - ord('0')]))\n",
    "                pre = 1\n",
    "            elif pre != 0 and change[ord(x) - ord('0')] == ord(x) - ord('0'):\n",
    "                ans.append(chr(ord('0') + change[ord(x) - ord('0')]))\n",
    "            else:\n",
    "                if pre == 1:\n",
    "                    pre = 0\n",
    "                ans.append(x)\n",
    "\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        num = list(num)\n",
    "        for i in range(n):\n",
    "            # 寻找第一个突变后数值更大的位作为左边界\n",
    "            if change[int(num[i])] > int(num[i]):\n",
    "                # 尝试更新右边界\n",
    "                while i < n and change[int(num[i])] >= int(num[i]):\n",
    "                    num[i] = str(change[int(num[i])])\n",
    "                    i += 1\n",
    "                break\n",
    "        return ''.join(num)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        num = list(num)\n",
    "        n = len(num)\n",
    "        left = 0\n",
    "        while(left < n):\n",
    "            if(change[int(num[left])] <= int(num[left])):\n",
    "                left += 1\n",
    "            else:\n",
    "                num[left] = str(change[int(num[left])])\n",
    "                right = left + 1\n",
    "                while(right < n and change[int(num[right])] >= int(num[right])):\n",
    "                    num[right] = str(change[int(num[right])])\n",
    "                    right += 1\n",
    "                break\n",
    "        return ''.join(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        num = list(num)\n",
    "        n = len(num)\n",
    "        left = 0\n",
    "        while(left < n):\n",
    "            if(change[int(num[left])] <= int(num[left])):\n",
    "                left += 1\n",
    "            else:\n",
    "                num[left] = str(change[int(num[left])])\n",
    "                right = left + 1\n",
    "                while(right < n and change[int(num[right])] >= int(num[right])):\n",
    "                    num[right] = str(change[int(num[right])])\n",
    "                    right += 1\n",
    "                break\n",
    "        return ''.join(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        num = list(num)\n",
    "        for i in range(n):\n",
    "            # 寻找第一个突变后数值更大的位作为左边界\n",
    "            if change[int(num[i])] > int(num[i]):\n",
    "                # 尝试更新右边界\n",
    "                while i < n and change[int(num[i])] >= int(num[i]):\n",
    "                    num[i] = str(change[int(num[i])])\n",
    "                    i += 1\n",
    "                break\n",
    "        return ''.join(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        nums = list(num)\n",
    "    \n",
    "        for i in range(n):\n",
    "            if change[int(nums[i])] > int(nums[i]):\n",
    "                while i < n and change[int(nums[i])] >= int(nums[i]):\n",
    "                    nums[i] = str(change[int(nums[i])])\n",
    "                    i += 1\n",
    "                break\n",
    "        return ''.join(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n, num = len(num), list(num)\n",
    "        for i in range(n):\n",
    "            # 寻找第一个突变后 数值更大的位作为左边界\n",
    "            if change[int(num[i])] > int(num[i]):\n",
    "                # 尝试更新 右边界\n",
    "                while i < n and change[int(num[i])] >= int(num[i]):\n",
    "                    num[i] = str(change[int(num[i])])\n",
    "                    i += 1\n",
    "                break\n",
    "        return ''.join(num)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        num = list(num)\n",
    "        for i in range(n):\n",
    "            if change[int(num[i])] > int(num[i]):\n",
    "                while i < n and change[int(num[i])] >= int(num[i]):\n",
    "                    num[i] = str(change[int(num[i])])\n",
    "                    i += 1\n",
    "                break\n",
    "        return ''.join(num)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 贪心\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        num = list(num)\n",
    "        for i in range(n):\n",
    "            # 寻找第一个突变后数值更大的位作为左边界\n",
    "            if change[int(num[i])] > int(num[i]):\n",
    "                # 尝试更新右边界\n",
    "                while i < n and change[int(num[i])] >= int(num[i]):\n",
    "                    num[i] = str(change[int(num[i])])\n",
    "                    i += 1\n",
    "\n",
    "                break\n",
    "                \n",
    "        return ''.join(num)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        changed = False\n",
    "        num = list(num)\n",
    "        for i, c in enumerate(num):\n",
    "            if int(c) < change[int(c)]:\n",
    "                while i < len(num) and int(num[i]) <= change[int(num[i])]:\n",
    "                    num[i] = str(change[int(num[i])])\n",
    "                    i += 1\n",
    "                break\n",
    "        return ''.join(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        num = list(num)\n",
    "        ok = False\n",
    "        for i, d in enumerate(num):\n",
    "            d = int(d)\n",
    "            if d < change[d]:\n",
    "                ok = True\n",
    "                num[i] = str(change[d])\n",
    "            elif ok and d > change[d]:\n",
    "                break\n",
    "        return ''.join(num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        num_list = list(num)\n",
    "        found = False\n",
    "        for i in range(len(num_list)):\n",
    "            digit = int(num_list[i])\n",
    "            if change[digit] > digit:\n",
    "                num_list[i] = str(change[digit])\n",
    "                found = True\n",
    "            elif change[digit] == digit:\n",
    "                continue\n",
    "            elif found:\n",
    "                break\n",
    "        return ''.join(num_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        flag = True # 表示还不需要进行改变，如果有第一次改变变为False此后一旦遇到改变后会变小的就直接返回结果\n",
    "        num = list(num)\n",
    "        for i, x in enumerate(num):\n",
    "            dig = int(x)\n",
    "            if change[dig] > dig:\n",
    "                flag = False\n",
    "                num[i] = str(change[dig])\n",
    "            if not flag and change[dig] < dig:\n",
    "                break\n",
    "        return ''.join(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        num = list(num)\n",
    "        n = len(num)\n",
    "        left = 0\n",
    "        while(left < n):\n",
    "            if(change[int(num[left])] <= int(num[left])):\n",
    "                left += 1\n",
    "            else:\n",
    "                num[left] = str(change[int(num[left])])\n",
    "                right = left + 1\n",
    "                while(right < n and change[int(num[right])] >= int(num[right])):\n",
    "                    num[right] = str(change[int(num[right])])\n",
    "                    right += 1\n",
    "                break\n",
    "        return ''.join(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\r\n",
    "        n = len(num)\r\n",
    "        num = list(num)\r\n",
    "        for i in range(n):\r\n",
    "            if change[int(num[i])] > int(num[i]):\r\n",
    "                j = i\r\n",
    "                while j < n and change[int(num[j])] >= int(num[j]):\r\n",
    "                    num[j] = str(change[int(num[j])])\r\n",
    "                    j += 1\r\n",
    "                break\r\n",
    "        return ''.join(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n=list(num)\n",
    "        for i,v in enumerate(n):\n",
    "            if change[int(v)]>int(v):\n",
    "                for j in range(i,len(n)):\n",
    "                    if change[int(n[j])]>=int(n[j]):\n",
    "                        n[j]=str(change[int(n[j])])\n",
    "                    else:\n",
    "                        return ''.join(n)\n",
    "                return ''.join(n)\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        num = list(num)\n",
    "\n",
    "        for i in range(len(num)):\n",
    "            if change[int(num[i])] > int(num[i]):\n",
    "                for j in range(i, len(num)):\n",
    "                    if change[int(num[j])] >= int(num[j]):\n",
    "                        num[j] = str(change[int(num[j])])\n",
    "                    else:\n",
    "                        break\n",
    "                break\n",
    "\n",
    "        return ''.join(num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        more, equal = set(), set()\n",
    "        for i, j in enumerate(change):\n",
    "            if j > i:\n",
    "                more.add(i)\n",
    "            elif j == i:\n",
    "                equal.add(i)\n",
    "        start = -1\n",
    "        for i, j in enumerate(num):\n",
    "            if int(j) in more:\n",
    "                start = i \n",
    "                break \n",
    "        if start == -1:\n",
    "            return num\n",
    "        ans = list(num)\n",
    "        for i in range(start, n):\n",
    "            if int(num[i]) in more or int(num[i]) in equal:\n",
    "                ans[i] = str(change[int(num[i])])\n",
    "            else:\n",
    "                break \n",
    "        return ''.join(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        num = list(num)\n",
    "        for i in range(n):\n",
    "            # 寻找第一个突变后数值更大的位作为左边界\n",
    "            if change[int(num[i])] > int(num[i]):\n",
    "                # 尝试更新右边界\n",
    "                while i < n and change[int(num[i])] >= int(num[i]):\n",
    "                    num[i] = str(change[int(num[i])])\n",
    "                    i += 1\n",
    "                break\n",
    "        return ''.join(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        n = len(num)\n",
    "        num = list(num)\n",
    "        for i in range(n):\n",
    "            # 寻找第一个突变后数值更大的位作为左边界\n",
    "            if change[int(num[i])] > int(num[i]):\n",
    "                # 尝试更新右边界\n",
    "                while i < n and change[int(num[i])] >= int(num[i]):\n",
    "                    num[i] = str(change[int(num[i])])\n",
    "                    i += 1\n",
    "                break\n",
    "        return ''.join(num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        flag = True # 表示还不需要进行改变，如果有第一次改变变为False此后一旦遇到改变后会变小的就直接返回结果\n",
    "        num = list(num)\n",
    "        for i, x in enumerate(num):\n",
    "            dig = int(x)\n",
    "            if change[dig] > dig:\n",
    "                flag = False\n",
    "                num[i] = str(change[dig])\n",
    "            if not flag and change[dig] < dig:\n",
    "                break\n",
    "        return ''.join(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        ans=[]\n",
    "        c=True\n",
    "        first=False\n",
    "        for ch in num:\n",
    "            if not first and  int(ch)>=change[int(ch)]:\n",
    "                ans.append(ch)\n",
    "                continue\n",
    "            else:\n",
    "                first=True\n",
    "            if c and first:\n",
    "                if int(ch)<=change[int(ch)]:\n",
    "                    ans.append(str(change[int(ch)]))\n",
    "                else:\n",
    "                    ans.append(ch)\n",
    "                    c=False\n",
    "            else:\n",
    "                ans.append(ch)\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        ans = list(num)\n",
    "        started = False\n",
    "        for i in range(len(num)):\n",
    "            x = int(num[i])\n",
    "            if change[x] >= x:\n",
    "                ans[i] = str(change[x])\n",
    "                if change[x] > x:\n",
    "                    started = True\n",
    "            elif started:\n",
    "                break\n",
    "\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumber(self, num: str, change: List[int]) -> str:\n",
    "        flag = True # 表示还不需要进行改变，如果有第一次改变变为False此后一旦遇到改变后会变小的就直接返回结果\n",
    "        num = list(num)\n",
    "        for i, x in enumerate(num):\n",
    "            dig = int(x)\n",
    "            if change[dig] > dig:\n",
    "                flag = False\n",
    "                num[i] = str(change[dig])\n",
    "            if not flag and change[dig] < dig:\n",
    "                break\n",
    "        return ''.join(num)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
